• Serif
  • Sans

SQlite源码分析

Bitvec.c介绍

      我们知道在使用数据库的时候不能 直接修改磁盘上的数据，而是先将数据从磁盘读入到内存的datacache，然后在内存中修改（被修改过的页称为脏数据页），最后再通过检查点Checkpoint将脏数据页从当前数据库的缓冲区高速缓存刷新到磁盘上，具体过程如图。       而“bitvec”对象，作为页面缓存的一部分，就是用来追踪那些已记录在日志 的页面（也就是脏页），以提高速度和减少内存的消耗，特别是对于一些大的数据库文件。它实现了用一个对象来表示一个固定长度的位图（Bit-map）。一个位图就是用来记录在一个事务处理过程中数据库的哪些页被日 志记录，或者哪些页有"dont-write"的性质。通常只有很少的页满足条件，因此位图通常很稀少，并且基数小。但是有时（比如当丢弃一个大的表时）数据库中绝大多数或所有的页都会被日志记录。在这种情况下，位图是稠密的，并且基数大。所以，算法应该能够很好的处理这两种情况。
      所谓位图（Bit-map），就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。它是一种很特殊的数据结构，比如可以利用位图来排序，先将问题映射到位串上，对位串进行处理后，再将位串逆射到问题空间上。但是这种排序方法对输入的数据是有比较严格的要求(数据不能重复，大致知道数据的范围)。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。
      老的位图处理脏页的方式限制了SQLite的最大容量是GB的单位范围，而不是理论上的TB的单位范围，因为它在每个事务处理之前都强制为数据库的每1M分配256 bits来追踪脏页，而位图的大小是与数据库的大小成正比的，所以随着数据库的增大，每个事务处理前给位图分配的内存空间也在增大。比如当你一个数据库达到了GB的范围，你就得给每次事务分配MB范围的脏页位图内存了。但是现在不是再去用一个静态的位图去处理脏页，而是有了一个bitvec类，实现了稀疏矩阵，消除了大部分情况下对内存大小的依赖。但要注意的是，bitvec可以大大减少内存的使用是在平均情况下，它改变不了最坏的情况，如果有一个事务涉及很多的页面（比如当丢弃一个大的表时），bitvec结构仍然会非常大。一般Bitvec结构的大小是在事务开始时数据库文件中的页的数量，因此通常不到几千比特。